Join dependency

A join dependency is a constraint on the set of legal relations over a database scheme. A table T is subject to a join dependency if T can always be recreated by joining multiple tables each having a subset of the attributes of T. If one of the tables in the join has all the attributes of the table T, the join dependency is called trivial.

The join dependency plays an important role in the Fifth normal form, also known as project-join normal form, because it can be proven that if you decompose a scheme R in tables R_1 to R_n, the decomposition will be a lossless-join decomposition if you restrict the legal relations on R to a join dependency on R called *(R_1,R_2,...R_n).

Another way to describe a join dependency is to say that the set of relationships in the join dependency is independent of each other.

Contents

Formal definition

Let R be a relation schema and let R_1, R_2, ..., R_n be a decomposition of R.
The relation r(R) satisfies the join dependency *(R_1,R_2,...R_n) if \bowtie_{i = 1}^n \Pi_{R_i}(r) = r.
A join dependency is trivial if one of the R_i is R itself. [1]

Example

Given a pizza-chain that models purchases in table Customer = { order-number, customer-name, pizza-name, delivery-boy }. It is obvious that you can derive the following relations:

Since the relationships are independent you can say there is a join dependency as follows: *((order-number, customer-name), (order-number, pizza-name), (order-number,delivery-boy)).

If each customer has his own delivery-boy however, you could have a join-dependency like this: *((order-number, customer-name), (order-number, delivery-boy), (customer-name, delivery-boy), (order-number,pizza-name)), but *((order-number, customer-name, delivery-boy), (order-number,pizza-name)) would be valid as well. This makes it obvious that just having a join dependency is not enough to normalize a database scheme.

See also

References

  1. ^ Silberschatz, Korth. Database System Concepts, 1st Edition